The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
In conventional packet forwarding, a packet is transmitted through a network from one router in the network to the next, where each router independently analyzes the packet header and makes an independent forwarding decision for the packet. More specifically, each router chooses a next hop router for the packet based on the packet header and on the results of a routing algorithm run by the router. In choosing the next hop router for a particular packet, each router first determines the destination address prefix to which the packet is sent, and then maps the destination address to the address of a router that is the next hop in the path to that destination.
The Multi-Protocol Label Switching (MPLS) protocol and the underlying architecture are described in RFC3031, which was published by the Internet Engineering Task Force (IETF) in January 2001, and which is hereby incorporated by reference for all purposes as if fully set forth herein. In MPLS packet forwarding, the determination of the destination address of each transmitted packet is done just once—at the ingress router, established at an edge of the network, at which the packet enters the network. Typically, the destination address would map to the network address of an egress router, also established at an edge of the network, at which the packet exits the network. At the ingress router, the destination address of the packet is indicated by a fixed-length, locally significant identifier that is referred to as an “MPLS label” or simply “label”. When the ingress router receives an inbound packet, the router determines the label indicating the destination address for the packet based on information included in the packet header. The ingress router then creates a label stack that stores the looked-up label at the top. (As referred to herein, a “label stack” is a data structure that stores an ordered set of one or more MPLS labels.) Before the ingress router forwards the packet to its next hop, the ingress router attaches (prepends) the label stack to the beginning of the packet. The routers at subsequent hops do not perform any further analysis of the packet header; rather, each router at any subsequent hop uses the top label in the label stack as an index into a table and determines a table record which specifies the address of the next hop router for that particular label and a new top label. The router then swaps, or replaces, the top label in the packet label stack with the new top label from the table record, and forwards the packet to the next hop router. (In some implementations, MPLS forwarding may use the so called “penultimate hop popping” technique to process the label stack at the penultimate router that immediately precedes the egress router—instead of swapping a new top label onto the label stack, the penultimate router simply pops the top label from the label stack before sending the packet to the egress router.)
In a typical MPLS implementation, the destination address of an inbound packet received at an ingress router is associated with the Border Gateway Protocol (BGP) next hop address for the packet, where the BGP next hop address is the address of the egress router at which the packet must exit the network. Typically, the ingress router learns the BGP next hop address from the egress router over a BGP session, and stores the BGP next hop address in one or more routing tables. In the routing tables, a BGP next hop address is typically associated with an Internal Gateway Protocol (IGP) label, which indicates a Label Switched Path (LSP) to the router at the next hop and, ultimately, leads to the egress router. An LSP is a path in the network between two routers that support MPLS forwarding, also known as “Label Switching Routers” (LSRs). An LSR in a particular LSP uses an IGP label to identify its adjacent LSR as the next hop router for packets sent along that LSP. An IGP label (which may also be referred to as an “LDP label”) is an MPLS label that is locally significant between two LSRs; an upstream LSR typically receives the IGP label identifying an LSP from a downstream LSR over a Label Distribution Protocol (LDP).
Since in MPLS forwarding intermediate routers do not need to analyze packet headers and to run routing algorithms for each received packet, MPLS forwarding is generally faster than conventional packet forwarding for routing transit traffic across a network. For this reason, in a typical implementation, MPLS forwarding is used to route transit traffic across the network or networks of an Autonomous System (AS), where the transit traffic typically originates in, and is destined to, networks that are outside the AS. Examples of such AS networks include, but are not limited to, telecommunication networks and Internet Service Provider (ISP) networks that route network traffic originating from customer networks to any network destinations that are reachable through the telecommunication or ISP networks. Because in such typical MPLS forwarding implementations only the ingress routers perform packet header analysis on inbound packets, the performance of the ingress routers affects the performance of the entire AS network. For example, ingress routers in a typical ISP network may need to process and forward inbound packets at rates of 16 million packets per second and above.
In order to achieve forwarding at such high rates, router platforms typically provide hardware components for analyzing packet headers and making forwarding decisions. Examples of such router platforms include the Gigabit Switch Router (GSR) 12000 Series provided by Cisco Systems, Inc. of San Jose, Calif. The architecture of the Cisco 12000 Series routers is truly distributed and is provided on a hardware platform in which a gigabit route processor and multiple line cards are coupled over a crossbar switch fabric. Each line card is capable of performing forwarding functions independently, and includes its own processor and Application-Specific Integrated Circuits (ASICs) that are configured to process inbound packets and to make forwarding decisions. Each line card also includes its own memory for storing copies of Forwarding Information Base (FIB) tables that are computed by the gigabit route processor. For each packet received at a communication link interface of a line card, the line card ASICs perform independent lookup of the packet destination address in the line card FIB tables. Thereafter, the packet is switched across the crossbar switch fabric to the destination line card of the router.
However, several factors affect the ability of hardware components to process inbound network packets at the rates at which the packets are received. One of these factors is the amount of routing and forwarding information that is programmed in the router or line card memory. For example, for the purpose of MPLS forwarding, an ingress router established at the edge of an ISP network may need to store over half a million address prefixes to which MPLS traffic can be forwarded. (An address prefix may be expressed as a combination of a network address and a mask that indicates the bits of the address used to identify the network portion of the address.) Since the amount of fast memory in the router or line card is finite, the sheer scale of the routing and forwarding information that needs to be maintained affects the manner in which this information is stored in memory, which in turn affects how fast the hardware components can access this information.
Other factors, which affect the ability of hardware components to process inbound network packets at the rates at which the packets are received, involve the limitations of the hardware components themselves. For example, hardware components that make forwarding decisions can perform only a limited number of memory accesses for each received packet at the rate at which packets are received. The forwarding hardware components in most high capacity routers are capable of performing only a single memory access per packet at the rates at which packets are received by the routers. The forwarding ASICs in some line cards for the Cisco 12000 Series routers are capable of performing two memory accesses per packet at the maximum line card receiving rate.
These memory access limitations of the forwarding hardware components are apparent in routers performing MPLS forwarding for types of network traffic that need multiple memory accesses for making a forwarding decision. Examples of such types of network traffic include, but are not limited to, VPN traffic, Internet Protocol version 4 (IPv4) traffic, and IPv6 traffic. In addition, the memory access limitations of the forwarding hardware components are especially apparent in routers that are configured to perform MPLS forwarding in conjunction with network load-balancing and/or load-sharing because load-balancing and load-sharing may require even more memory accesses per packet for making a forwarding decision.
Other factors, which affect the ability of hardware components to process inbound network packets at the rates at which the packets are received, include the ability of the routers or line cards to modify the routing and forwarding information in memory at acceptably high rates without sacrificing the forwarding performance. For example, an ISP network may experience failures (or “flaps”) on one or more IGP paths that are established between any of its ingress, intermediate, and egress routers. When an IGP path flaps, one or more of the affected routers typically compute new network routes around the flapped path and distribute these new routes to the affected routers over one or more IGP or internal BGP (iBGP) protocols. (A route comprises an address destination, which is usually represented by an address prefix, and information that describes the path to that address destination; in a network, the process of computing, distributing, and installing new routes at network infrastructure elements is referred to as “route convergence”. Examples of IGP protocols include, but are not limited to, the Routing Information Protocol (RIP) and the Open Shortest Path First (OSPF) protocol.) From the perspective of an ingress router that provides MPLS forwarding over established LSPs, an IGP path flap between any two routers in the network would affect all LSPs that are established over the failed path. Thus, after an IGP path flap, the ingress router may receive numerous new routes and other routing information changes that affect the ingress router's LSPs, and the ingress router and/or line cards thereof need to update the routing information stored in memory at rates that are high enough and do not hinder forwarding performance.
Based on the foregoing, techniques are clearly needed for fast route convergence at ingress routers. Techniques are also clearly needed for storing routing and forwarding information in a router or line card in a manner that would provide unhindered forwarding performance while at the same time overcoming the memory access limitations of the hardware components that make the forwarding decisions.